# 打家劫舍： https://leetcode-cn.com/problems/house-robber/

class Solution:
    def rob(self, nums: list) -> int:
        """
            [1,2,3,1]，根据题目要求， 开始时，一定是偷 nums[0] 或者是 nums[1] 才能保证偷盗最多，因为假如偷 nums[2]
            那么 就少偷了一个 nums[0] , 根据上面的结论，每偷 nums[i], 必须偷 nums[i+2], 或者nums[i + 3] 才能保证最后偷到的最多
            那么就抽象成一颗二叉树了， 每次有两种偷的选择，全排列所有偷法，找出最大的

                                    -2    
                            0               1
                        2         3     3          4
                    4       5   5  6  5   6     6     7
            另外观察可以知道，越往后重复计算越多，效率也很低，所以可以缓存计算过的节点值
        """
        n = len(nums)
        ans = 0
        cache = dict()
        def dfs(nums, index, total):
            """
                param:  index: 当前偷的哪家的下标
                param:  total: 当前偷的总金额
            """
            nonlocal ans

            if index >= n: 
                ans = max(ans, total)
                return 
            
            # 计算当前位置能偷多少钱
            if index in cache:  
                total = cache.get(index)
            else:
                amount = nums[index] if index >= 0 else 0
                total += amount
                cache[index] = total
            # 去下一家偷
            dfs(nums, index + 2, total)
            dfs(nums, index + 3, total)

        dfs(nums, -2, 0)

        return ans


# 全排列竟然是我想出来的~ ，但是感觉 cache 用的有些疑惑呀现在看来，并且时间复杂度过高，官网的动态规划
class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0

        size = len(nums)
        if size == 1:
            return nums[0]
        
        dp = [0] * size
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, size):
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
        
        return dp[size - 1]


nums = [1,2,1,1]

s = Solution()
rst = s.rob(nums)
print(rst)




